package com.sheng.leetcode.year2023.month08.day10;

import org.junit.Test;

/**
 * @author by ls
 * @date 2023/8/10
 * <p>
 * 1289. 下降路径最小和 II<p>
 * <p>
 * 给你一个 n x n 整数矩阵 grid ，请你返回 非零偏移下降路径 数字和的最小值。<p>
 * 非零偏移下降路径 定义为：从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。<p>
 * <p>
 * 示例 1：<p>
 * 输入：grid = [[1,2,3],[4,5,6],[7,8,9]]<p>
 * 输出：13<p>
 * 解释：<p>
 * 所有非零偏移下降路径包括：<p>
 * [1,5,9], [1,5,7], [1,6,7], [1,6,8],<p>
 * [2,4,8], [2,4,9], [2,6,7], [2,6,8],<p>
 * [3,4,8], [3,4,9], [3,5,7], [3,5,9]<p>
 * 下降路径中数字和最小的是 [1,5,7] ，所以答案是 13 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：grid = [[7]]<p>
 * 输出：7<p>
 * <p>
 * 提示：<p>
 * n == grid.length == grid[i].length<p>
 * 1 <= n <= 200<p>
 * -99 <= grid[i][j] <= 99<p>
 */
public class LeetCode1289 {

    @Test
    public void test01() {
        int[][] grid = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
//        int[][] grid = {{7}};
        System.out.println(new Solution().minFallingPathSum(grid));
    }
}

class Solution {
    public int minFallingPathSum(int[][] grid) {
        // 非零偏移下降路径：满足与上一行不在同一列即可
        if (grid.length == 1) {
            return grid[0][0];
        }
        int n = grid.length;
        // 满足条件的最小值
        int min = Integer.MAX_VALUE;
        int[][] dp = new int[n][n];
        // 将 grid[0] 的第一个数组复制到 dp[0] 的第一个数组
        System.arraycopy(grid[0], 0, dp[0], 0, n);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int m = Integer.MAX_VALUE;
                // 获取当前行与上一位处于不同位置的元素的最小值
                for (int k = 0; k < n; k++) {
                    if (j != k && m > dp[i - 1][k]) {
                        m = dp[i - 1][k];
                    }
                }
                // 添加当前值，和下一行的最小值
                dp[i][j] += m + grid[i][j];
            }
        }
        // 判断最小值
        for (int i = 0; i < n; i++) {
            if (min > dp[n - 1][i]) {
                min = dp[n - 1][i];
            }
        }
        return min;
    }
}
